perm filename LET.ABS[NOT,DBL]1 blob
sn#195047 filedate 1976-01-02 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00004 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .!XGPCOMMANDS←"/PMAR=2200"
C00004 00003 Scientists often face the difficult
C00015 00004 .GROUP SKIP 1 SELECT 7 INDENT 0,6,0 PREFACE 1 COMPACT
C00020 ENDMK
C⊗;
.!XGPCOMMANDS←"/PMAR=2200"
.DEVICE XGP
.FONT 1 "BASL30"
.FONT 2 "BASB30"
.FONT 4 "BASI30"
.FONT 5 "BDR40"
.FONT 6 "NGR25"
.FONT 7 "NGR20"
.FONT 8 "GRK30"
.FONT A "SUP"
.FONT B "SUB"
.TURN ON "↑α↓_π[]{"
.TURN ON "⊗" FOR "%"
.TURN ON "@" FOR "%"
.PAGE FRAME 59 HIGH 83 WIDE
.AREA TEXT LINES 1 TO 58
.COUNT PAGE PRINTING "1"
.TABBREAK
.ODDLEFTBORDER←EVENLEFTBORDER←1000
.AT "ffi" ⊂ IF THISFONT ≤ 4 THEN "≠" ELSE "fαfαi" ⊃;
.AT "ffl" ⊂ IF THISFONT ≤ 4 THEN "α∞" ELSE "fαfαl" ⊃;
.AT "ff" ⊂ IF THISFONT ≤ 4 THEN "≥" ELSE "fαf" ⊃;
.AT "fi" ⊂ IF THISFONT ≤ 4 THEN "α≡" ELSE "fαi" ⊃;
.AT "fl" ⊂ IF THISFONT ≤ 4 THEN "∨" ELSE "fαl" ⊃;
.SELECT 1
.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
.MACRO E ⊂ APART END ⊃
.MACRO FAD ⊂ FILL ADJUST DOUBLE SPACE PREFACE 2 ⊃
.MACRO FAS ⊂ FILL ADJUST SINGLE SPACE PREFACE 1 ⊃
.FAS
.COMPACT
.SELECT 1
.PORTION THESIS
.PAGE←0
.NEXT PAGE
.INDENT 0
.TURN OFF "{∞→}"
.BEGIN CENTER
⊗5↓_Automated Math Theory Formation_↓⊗*
⊗2Douglas B. Lenat⊗*
Artificial Intelligence Lab
Stanford University
Stanford, California 94305
.END
Scientists often face the difficult
task of formulating research problems which must be soluble
yet nontrivial. In any given branch of science, it is usually easier to tackle a
specific given problem than to propose interesting yet managable new
questions to investigate. For example, contrast ⊗4solving⊗* the
Missionaries and Cannibals problem with the more ill-defined
reasoning which led to ⊗4inventing⊗* it.
For my dissertation, I am investigating creative theory formation in
mathematics: how to propose interesting new concepts and plausible
hypotheses connecting them. The experimental vehicle of my research
is a computer program called ⊗2AM⊗* (for ⊗2↓_A_↓⊗*utomated
⊗2↓_M_↓⊗*athematician), which carries out some of the activities involved
in mathematical research: noticing simple relationships in empirical data,
formulating new definitions out of existing ones, proposing some
plausible conjectures (and, less importantly, sometimes proving them),
and evaluating the aesthetic "interestingness" of new concepts.
Before discussing how to ⊗4synthesize⊗* a new theory, consider briefly
how to ⊗4analyze⊗* one, how to construct a plausible chain of
reasoning which terminates in a given discovery. One can do this
by working backwards, by reducing the creative act to simpler and simpler
creative acts.
For example,
consider the concept of prime numbers. How might one be led to
define such a notion? Notice the following plausible strategy:
.ONCE INDENT 9,9,9
"If f is a function which transforms elements of A into
elements of B, and B is ordered, then consider just those members of A
which are transformed into ⊗4extremal⊗* elements of B.
This set is an interesting subset of A."
When f(x) means "factors of x", and the ordering is "by length", this
heuristic says to consider those numbers which have a minimal⊗A1⊗* number
of factors -- that is, the primes.
So this rule actually ⊗4reduces⊗* our task from "proposing the concept of
prime numbers" to the more elementary problems of "inventing factorization"
and "discovering cardinality".
But suppose we know this general rule:
"If f is an interesting function, consider its inverse."
It reduces the task of discovering factorization to the simpler
task of discovering multiplication.
Eventually, this task reduces to the discovery of very basic notions, like
substitution, set-union, and
equality. To explain how a given researcher might have made a given
discovery, such an analysis is continued until that inductive task is
reduced to "discovering" notions which the researcher already knew.
Suppose a large collection of these heuristics has been
assembled (e.g., by analyzing a great many discoveries, and writing down
new heuristic rules whenever necessary).
Instead of using them to ⊗4explain⊗* how a given idea might have
evolved, one can imagine
starting from a basic core of knowledge and
"running" the
heuristics to ⊗4generate⊗* new concepts.
Such syntheses are precisely what AM does.
The program consists of
a corpus of primitive mathematical concepts and a collection of guiding
heuristics.
AM's activities all serve to expand AM itself,⊗A2⊗* to enlarge upon a
given body of mathematical knowledge.
To cope with the enormity of
the potential "search space" involved,
AM uses its heuristics as judgmental criteria to guide
development in the most promising direction.
It appears that the process of inventing worthwhile new⊗A3⊗* concepts can be guided
successfully using a collection of a few hundred such heuristics.
Each concept is represented as a ⊗6BEING⊗*⊗A4⊗*, a frame-like data structure
with 30 different
facets or slots.
The types of slots include:
⊗6Examples, Definitions, Generalizations, Utility, Analogies,
Interestingness, Uninterestingness,⊗* and a couple dozen others.
The ⊗6BEINGs⊗*
representation provides a convenient scheme for organizing the
heuristics; for example, the following strategy
fits into the ⊗4Examples⊗* slot of the
⊗4Predicate⊗* concept:
"If, empirically,
10 times as many elements ⊗4fail⊗* some predicate P, as ⊗4satisfy⊗* it, then
some ⊗4generalization⊗* (weakened version) of P might be more interesting than P".
AM considers this suggestion after trying to fill in examples of any predicate.⊗A5⊗*
AM is initially given a large collection of core concepts, with only a few slots
filled in for each. Its sole activity is to choose some facet of
some concept, and fill in that particular slot. In so doing, new
notions will often emerge. Uninteresting ones are forgotten, mildly
interesting ones are kept as parts of one slot of one concept, and
very interesting ones are granted full concept status. Such new
⊗6Beings⊗* will have dozens of blank parts, hence the space of
possible actions (slots to fill in) grows rapidly.
The same heuristics are used both to suggest new directions for
investigation, and to limit attention: both to grow and to prune.
The particular mathematical domains in which AM operates depend on the choice of
initial concepts. Currently, AM is given about a hundred concepts, all of
which are what Piaget might describe as ⊗4prenumerical⊗*:
Sets, substitution, relations, equality, and so on. In particular, AM is not
told anything about proof, single-valued functions,
or numbers. Although it was never able to ⊗4prove⊗* the unique factorization
theorem, AM actually did ⊗4conjecture⊗* it.⊗A6⊗* Before this, AM had to
define and investigate
concepts corresponding to those we refer to as cardinality,
multiplication, factors, and primes,
based on reasoning similar to that in the example above.
The main difficulty with AM at present is getting it to accurately judge
⊗4a priori⊗* the value of each new concept, to quickly lose interest
in concepts which aren't going to develop into anything.
As with many AI programs, one aspect of working on AM is the
degree of precision with which one's ideas must be formulated.
The resultant body of detailed heuristics may be the germ of a more efficient
programme for educating math students than the current dogma.⊗A7⊗*
But perhaps the most exciting prospect opened up by AM is that
of experimentation: one could vary the concepts AM starts with, vary the
heurisitics available, etc., and study the effects on AM's behavior.
AM is a dissertation project ⊗4in progress⊗*; few conclusions have been drawn
yet.
.GROUP SKIP 1 SELECT 7 INDENT 0,6,0 PREFACE 1 COMPACT
*****************************************************************************************************************
↑1 The other extreme, numbers with a MAXIMAL number of factors, will
also be proposed as worth investigating. This leads to many
interesting questions; the only "new-to-Mankind"
mathematical result so far is
in fact that such maximally-divisible numbers must have the form
p⊗B1⊗*⊗Aa1⊗* p⊗B2⊗*⊗Aa2⊗* p⊗B3⊗*⊗Aa3⊗*... p⊗Bk⊗*⊗Aak⊗*, where the
p⊗Bi⊗*'s are the first k consecutive primes, and the exponents a⊗Bi⊗*
decrease with i, and the ratio of (a⊗Bi⊗*+1)/(a⊗Bj⊗*+1) is
approximately (as closely as is possibe for integers)
log(p⊗Bj⊗*)/log(p⊗Bi⊗*). For example, a typical divisor-rich number
is
n=2⊗A8⊗*3⊗A5⊗*5⊗A3⊗*7⊗A2⊗*11⊗A2⊗*13⊗A1⊗*17⊗A1⊗*19⊗A1⊗*23⊗A1⊗*29⊗A1⊗*31⊗A1⊗*37⊗A1⊗*41⊗A1⊗*43⊗A1⊗*47⊗A1⊗*53⊗A1⊗*.
The progression of its exponents+1 (9 6 4 3 3 2 2 2 2 2 2 2 2 2 2 2)
is about as close as one can get to satisfying the "logarithm"
constraint. This number n has 3,981,312
divisors. The "AM Conjecture" is that no number smaller than n has
that many divisors. By the way, this n equals 25,608,675,584.
↑2 Incidentally, these basic concepts include the operators which
enlarge the space (e.g., ⊗6COMPOSE-2-RELATIONS⊗* is both a concept in
its own right and a way to generate new ones).
↑3 Of course, "new" means new to AM, not to Mankind, and "worthwhile"
can only be judged in hindsight.
↑4 Lenat, Douglas, ↓_BEINGS: Knowledge as Interacting Experts_↓, 4th
IJCAI, 1975, pp. 126-133.
↑5 In fact, after AM attempts to find examples of SET-EQUALITY, so
few are found that AM decides to generalize that predicate. The
result is the predicate which means "Has-the-same-length-as" -- i.e.,
the rudiments of Cardinality.
↑6 Due to the firm base of preliminary concepts which AM developed,
this relationship was almost obvious. AM sought some predicate P
which, for each n, some member of FACTORS-OF(n) satisfied.
ALL-PRIMES was such a predicate. AM next constructed the relation
which associates, to each number n, all factorizations of n into
primes. The full statement of the UFT is simply that this relation
is a function; i.e., it is defined and single-valued for all numbers
n.
↑7 Currently, the educator takes the very best work any mathematician
has ever done, polishes it until its brilliance is blinding, and
presents it to the student to induce upon. A few individuals (e.g.,
Minsky and Papert at MIT, Adams at Stanford) are experimenting with
more realistic strategies for "teaching" creativity.